1. Field of the Invention
This invention relates to computer systems and telecommunication systems utilizing computers and more particularly to a method and apparatus for manipulating data to generate a cyclic redundancy check character, and for utilizing the cyclic redundancy check character generated and the data which it represents to ascertain that the data has not been altered.
2. Description of the Prior Art
A variety of different forms of error detection are built into data handling equipment. Such error detecting apparatus assume particular importance when data is transmitted from one particular device to another device within a data processing system or from one data processing system to another, where the probability of losing or obliterating several sequential bits is greater due to noise in transmission. Of course, changing even one bit would change the sense of an entire message.
Several schemes and devices have been utilized in error control. Perhaps the most common method of detecting errors is the use of parity. With this method, the digits of a binary word are inspected and an extra digit or bit (binary-digit) is added. This digit is chosen to be "zero" or "one", as necessary to keep the total number of digits in the "one" state either odd or even according to a predetermined convention. Another single-error correcting code is the Hamming code where parity checked digits are assigned to particular positions where their weights indicate which digits of the whole code are in error. Still other techniques utilize sum checks.
When information is transmitted through data links using public telephone networks or other such communication devices, the type of error encountered is different from those previously considered. Because the digits are transmitted serially, impulsive noise from the communication channel affects a sequence of adjacent digits as well. One technique utilizes a cyclic redundant check character for detecting such errors. In this technique a finite length of an original sequence of characters is divided by an operator to produce a remainder; the actual transmission comprises the original sequence followed by the remainder. At the receiver, a similar division process produces a locally generated remainder for comparison with that sent by the transmitter. Any differences result from the introduction of error sequences which cannot be divided exactly by the chosen operator.
In implementing this technique additional hardware is required both at the transmitting and receiving end. This hardware usually takes the form of an additional shift register, exclusive OR circuits and comparator. Since computer networks, where one computer system communicates with another, are beginning to mushroom, and since not all computer systems are equipped with this additional hardware, universal checking for transmission errors via this technique is not feasible unless the existing hardware of each existing computer system can be utilized to implement this technique.
One way of utilizing existing hardware is to provide software techniques that utilize a program for manipulation of the data to generate the character. However, such a scheme is too slow to keep up with the rate of transmission or reception and of utilization of modern-day data communication systems. What is needed is a control means and/or method for utilizing existing computer hardware at a rate greater than or equal to the rate of transmission or reception in generating and utilizing a cyclic redundant check character. Moreover, such control means and/or method should not require additional hardware, and should require only a modicum of modification to any computer system.